Currently, in many communication systems in operation or being investigated, error correction encoding is performed on transmission data in a transmitting-side apparatus in order to reduce degradation of transmission quality due to impediments such as interference or noise arising in a channel. A convolutional code is an error correction code that sequentially encodes information data using an encoder having storage, and is used in many communication systems due to such characteristics as having a simple encoder configuration and being able to perform encoding of information data of any length.
A self-orthogonal code, which is an error correction code, is one type of convolutional code that is characterized by the fact that parity bits corresponding to information bits are generated based on the condition that, in a plurality of parity check equations relating to respective information bits, only one information bit is included in two or more parity check equations. Use of this property enables majority logic decoding, which is a simple decoding method, to be used in decoding. Non-Patent Document 1 describes the background and logic of majority logic decoding, together with an actual decoding method.
Although a self-orthogonal code offers the advantage of easy apparatus implementation because it can be decoded with an extremely simple configuration by means of majority logic decoding, as stated above, the error correction capability of majority logic decoding is inferior to that of maximum-likelihood decoding using Viterbi decoding. Thus, a method whereby self-orthogonal code decoding is performed using a soft decision value, and a method whereby error correction capability is improved by applying iterative decoding in which decoding processing is repeated a plurality of times, have been proposed (see Patent Document 1 and Non-Patent Document 1). Furthermore, in order to improve the convergence characteristic in iterative decoding, a Self-Doubly Orthogonal Code has been proposed in which orthogonality is further added to a self-orthogonal code (see Patent Document 2).
Iterative APP (A Posteriori Probability) decoding of a self-orthogonal code is described below.
FIG. 1 shows a configuration of a J=6, K=18 self-orthogonal code encoder, where J corresponds to the number of parity check equations in which one information bit is included, and K corresponds to the constraint length. Encoder 10 shown in FIG. 1 is equipped with 17 (K−1) shift registers 11-1 through 11-17, and a parity bit is generated by modulo-2 addition (finding the exclusive OR) of shift register 11-1 input and the outputs of shift registers 11-2, 11-7, 11-13, 11-16, and 11-17 performed by modulo-2 adder 12.
Here, the connections between modulo-2 adder 12 and shift registers are represented as αj={0, 2, 7, 13, 16, 17} (where j=1, . . . , 6, and J=6). Also, i′th parity bit pi is represented by equation 1 using αj.
                    [        1        ]                                                                      p          i                =                              ∑                          k              =              1                        J                    ⁢                                          ⁢                      ⊕                                                  ⁢                          u                              i                -                                  α                  k                                                                                        (                  Equation          ⁢                                          ⁢          1                )            
Here, ui represents the i′th information bit, and ⊕ represents modulo-2 addition.
FIG. 2 shows parity check matrix H of this self-orthogonal code. In FIG. 2, Hs corresponds to a part corresponding to parity check matrix information bit ui, and Hp corresponds to a part corresponding to parity check matrix parity bit pi. The row direction of parity check matrix H represents a parity check equation, and the column direction represents an information bit or parity bit sequence.
Data that has undergone self-orthogonal encoding by encoder 10 in FIG. 1 undergoes digital modulation in a modulation section (not shown).
When BPSK (Binary Phase Shift Keying) is used as a digital modulation method, symbols corresponding to information bit ui and parity bit pi are represented by equations 2-1 and 2-2 respectively.
[2]xiu=−2ui+1  (Equation 2-1)xip=−2pi+1  (Equation 2-2)
A modulation symbol is received by a receiving-side apparatus via a channel. Assuming an AWGN (Additive White Gaussian Noise) channel, received modulation symbols are represented by equations 3-1 and 3-2 respectively, where niu and nip are additive white Gaussian noise components in accordance with average zero and variance σ2 distribution applied to xiu and xip.
[3]{circumflex over (x)}iu=xiu+niu  (Equation 3-1){circumflex over (x)}ip=xip+nip  (Equation 3-2)
In the case of a BPSK digital modulation method and an AWGN channel, received bit likelihoods are represented by equations 4-1 and 4-2. In equations 4-1 and 4-2, yiu and yip represent received bit likelihoods for information bit ui and parity bit pi respectively.
                    [        4        ]                                                                      y          i          u                =                              2            ⁢                                          x                ^                            i              u                                            σ            2                                              (                  Equation          ⁢                                          ⁢          4          ⁢                      -                    ⁢          1                )                                          y          i          p                =                              2            ⁢                                          x                ^                            i              p                                            σ            2                                              (                  Equation          ⁢                                          ⁢          4          ⁢                      -                    ⁢          2                )            
Information bit ui and parity bit pi received bit likelihoods yiu and yip are input to an iterative APP decoder.
FIG. 3 shows a configuration of an iterative APP decoder. Iterative APP decoder 20 in FIG. 3 comprises delay devices 21-1 through 21-M and 23-1 through 23-(M−1), APP decoding sections 22-1 through 22-M, and hard decision section 24. Delay devices 21-1 through 21-M and 23-1 through 23-(M−1) store received bit likelihoods, and output a received bit likelihood to each of APP decoding sections 22-1 through 22-M at timing at which each of APP decoding sections 22-1 through 22-M uses the relevant received bit likelihood.
APP decoding sections 22-1 through 22-M perform APP decoding processing using information bit and parity bit received bit likelihoods and an a posteriori probability value (APP value) obtained in the iteration before.
APP value λi(μ) in the μ'th iteration obtained by APP decoding section 22-μ is given by equation 5.
                    [        5        ]                                                                      λ          i                      (            μ            )                          =                              y            i            u                    +                                    ∑                              j                =                1                            J                        ⁢                                                  ⁢                          (                                                y                                      (                                          i                      +                                              α                        j                                                              )                                    p                                ·                                                      ∑                                          k                      =                      1                                                              j                      -                      1                                                        ⁢                                                                          ⁢                                      ·                                          λ                                              (                                                  i                          +                                                      α                            j                                                    +                                                      α                            k                                                                          )                                                                    (                                                  μ                          -                          1                                                )                                                              ·                                                                  ∑                                                  k                          =                          1                                                J                                            ⁢                                                                                          ⁢                                              λ                                                  (                                                      i                            +                                                          α                              j                                                        -                                                          α                              k                                                                                )                                                                          (                          μ                          )                                                                                                                                )                                                          (                  Equation          ⁢                                          ⁢          5                )            
Here, “∘” represents an add-min computation.
An add-min computation represents a computation given by equation 6. In equation 6, sgn(x) represents the positive/negative sign of x.
                    [        6        ]                                                                                  ∑                          j              =              1                        N                    ⁢                                          ⁢                      ·                          L              ⁡                              (                                  β                  j                                )                                                    =                                            (                              -                1                            )                                      N              +              1                                ⁢                                    ∏                              j                -                1                            N                        ⁢                                                  ⁢                                          sgn                (                                  L                  ⁡                                      (                                          β                      j                                        )                                                  )                            ⁢                                                min                                                            l                      =                      1                                        ,                    2                    ,                    …                    ⁢                                                                                  ,                    N                                                  ⁢                                  (                                                                                L                      ⁡                                              (                                                  β                          j                                                )                                                                                                  )                                                                                        (                  Equation          ⁢                                          ⁢          6                )            
Hard decision section 24 makes a hard decision for APP value λi(M) obtained by means of an M'th iteration. A hard decision is made based on the criterion in equation 7.[7]ûi=0 if and only if λi(M)>0, otherwise ûi=1  (Equation 7)
When iterative APP decoding is applied to self-orthogonal code decoding, decoding performance can be made to approach likelihood estimation performance as the number of iterations increases (see Non-Patent Document 2).
In investigations of decoding of a convolutional code using an iterative decoding algorithm, the use of an LDPC-CC (Low-Density Parity-Check Convolutional Code) has been investigated as well as the use of a self-orthogonal code.
An LDPC-CC is a convolutional code defined by a low-density parity check matrix, and is disclosed in Non-Patent Document 3 or Non-Patent Document 4. LDPC-CCs are divided into a number of groups according to differences in the parity check matrix design method. In the following description, an LDPC-CC designed on the basis of a Quasi-Cyclic Low-Density Parity-Check code (QC-LDPC code), which is a block code, disclosed in Non-Patent Document 4, is taken as an example.
Equation 8 shows a parity check matrix of a [21, 8, 6] QC-LDPC code.
                    [        8        ]                                                            H        =                  [                                                                      I                  1                                                                              I                  2                                                                              I                  4                                                                                                      I                  6                                                                              I                  5                                                                              I                  3                                                              ]                                    (                  Equation          ⁢                                          ⁢          8                )            
In parity check matrix H of equation 8, Ix represents a matrix in which rows of a 7×7 unitary matrix are cyclically shifted to the left by x. A [21, 8, 6] ° QC-LDPC code is a block code with a code length of 21.
To find an LDPC-CC from the QC-LDPC code shown in equation 8, block code parity check matrix H is replaced by a polynomial representation, and converted to a convolutional code parity check matrix. Equation 9 shows parity check matrix H(D) obtained by replacing Ix of parity check matrix H with delay operator Dx and creating a polynomial representation.
                    [        9        ]                                                                      H          ⁡                      (            D            )                          =                  [                                                    D                                                              D                  2                                                                              D                  4                                                                                                      D                  6                                                                              D                  5                                                                              D                  3                                                              ]                                    (                  Equation          ⁢                                          ⁢          9                )            
Dx is a delay operator in a polynomial representation, with exponent x of D representing a delay of point-in-time x. Since convolutional code parity check matrix H(D) and generator matrix G(D) satisfy the relationship in equation 10, generator matrix G(D) is as shown in equation 11.
                    [        10        ]                                                                                  G            ⁡                          (              D              )                                ⁢                                    H              ⁡                              (                D                )                                      T                          =        0                            (                  Equation          ⁢                                          ⁢          10                )                                [        11        ]                                                                      G          ⁡                      (            D            )                          =                  [                                                    D                +                                  D                  3                                                            1                +                                  D                  2                                +                                  D                  4                                                      ⁢            1            ⁢                                          D                2                                            1                +                                  D                  2                                +                                  D                  4                                                              ]                                    (                  Equation          ⁢                                          ⁢          11                )            
Generator matrix G(D) is a generator matrix for a recursive systematic convolutional code with a coding rate of ⅓.
FIG. 4 shows a configuration of an LDPC-CC encoder based on generator matrix G(D). LDPC-CC encoder 30 in FIG. 4 comprises delay devices 31-1 through 31-4 and modulo-2 adders 32 and 33. LDPC-CC encoder 30 is an encoder that outputs 3-bit codeword bits cmi (where m=1, 2, 3) for 1-bit information bit ui input. As can be seen from equation 11, c2i is equal to information bit ui.
FIG. 5 is an example in which parity check matrix H(D) given by equation 9 is described schematically by means of a matrix representation. FIG. 5 shows only parts of parity check matrix H(D) relating to a codeword bit of point-in-time i. Parity check matrix 40 in FIG. 5 is configured by repeatedly setting out partial matrix 41 comprising a plurality of 2×3 matrices. The 2×3 number of rows and number of columns correspond to the number of rows and number of columns of parity check matrix H(D) in polynomial representation form shown by equation 9. A column of partial matrix 41 corresponds to 3-bit codeword bits cmi output from LDPC-CC encoder 30 starting from the left.
In parity check matrix 40, three columns of point-in-time (c1i, c2i, c3i) are focused on. If a row in which “1” is placed in each column is extracted, it can be seen that the above self-orthogonal conditions are satisfied. For example, looking at the c1i column of parity check matrix 40, “1” is placed in the p1(i+1) and p2(i+6) rows, and in these two rows, columns in which “1” is placed other than c1i are {c3(i−3), c2(i−1), c2(i+1), c3(i+3)}, and the number of 1s is only one for each column.
Since an LDPC-CC can be designed so that a parity check matrix has self-orthogonality in this way, it is known to show an excellent error rate characteristic when iterative decoding is applied.    Patent Document 1: Japanese Patent Application Laid-Open No. 2002-111516    Patent Document 2: U.S. Pat. No. 6,167,552 Specification    Non-Patent Document 1: “Code Logic,” Hideki Imai, (IEICE, 1990 Annual Publication), p. 274-p. 278    Non-Patent Document 2: “Iterative Threshold Decoding Without Interleaving for Convolutional Self-Doubly Orthogonal Codes,” Cristian Cardinal, David Haccoun, Francois Gagnon, IEEE Transactions on Communications, vol. 51, no. 8, pp. 1274-1282 August 2003.    Non-Patent Document 3: “An Analysis of the Orthogonality Structures of Convolutional Codes for Iterative Decoding,” Yu-Cheng He, David Haccoun, IEEE Transactions on Information Theory, vol. 51, no. 9, pp. 3247-3261, September 2005.    Non-Patent Document 4: “Time-Varying Periodic Convolutional Codes With Low-Density Parity-Check-Matrix,” Alberto Jimenez Felstorom. and Kamil Sh. Zigangirov, IEEE Transactions on Information Theory, Vol. 45. No. 6. pp. 2181-2191. September 1999.    Non-Patent Document 5: “LDPC Block and Convolutional Codes Based on Circulant Matrices,” R. Michael Tanner, Deepak Sridhara, Arvind Sridharan, Thomas E. Fuja, and Daniel J. Costello. Jr., IEEE Transactions on Information Theory. vol. 50. no. 12. December 2004.